/**
 * @file sq_list.cpp
 * @brief 
 * @author lwl (lwl510ll@163.com)
 * @version 1.0
 * @date 2021-09-01
 * 
 * @copyright Copyright (c) 2021  LWL
 * 
 * @par 修改日志:
 * <table>
 * <tr><th>Date       <th>Version <th>Author  <th>Description
 * <tr><td>2021-09-01 <td>1.0     <td>LWL    <td>内容
 * </table>
 */
#include "sq_list.h"
#include <iostream>

using namespace std;

/**
 * @brief Construct a new Sq List:: Sq List object
 * 
 */
SqList::SqList()
{
    this->sq_list_header = new SqListElem;
    this->sq_list_length = 0;
}

SqList::~SqList()
{

    SqListElem *temp = this->sq_list_header;
    int sq_length = this->sq_list_length;

    while(sq_length)
    {
        this->DeletePos(sq_length);
        sq_length--;
    }
}

/**
 * @brief Create SqList by inserting head
 * 
 * @param length init sqList length 
 * @return true  create sqList success
 * @return false create sqList fail
 */
bool SqList::CreateHead(int length)
{
    elem temp = 0;

    cout << "创建的初始化链表为：" << length << endl;

    for(int i=0; i<length; i++)
    {
        SqListElem *s = new SqListElem;
        if(NULL == s)
        {
            cout << "申请内存失败\n" << "length: " <<  this->sq_list_length << endl;
            return false;
        } 
        s->data = i+1;
        s->sq_list_next= this->sq_list_header->sq_list_next;
        this->sq_list_header->sq_list_next = s;
        this->sq_list_length++;
    }
    return true;
}

bool SqList::CreateTail(int length)
{
    SqListElem *last_node = this->sq_list_header; // 用来保存最后一个节点
    
    for(int i=0; i<length; i++)
    {
        SqListElem *s = new SqListElem;
        if(NULL == s)
        {
            cout << "申请内存失败\n" << "length: " <<  this->sq_list_length << endl;
            return false;
        } 
        s->data = i+1;
        s->sq_list_next = last_node->sq_list_next;
        last_node->sq_list_next = s;
        last_node = s;
        this->sq_list_length++;
    }

    return true;
}

/**
 * @brief Query the date in sqList Pos 
 * 
 * @param data Query the date
 * @param pos  sqList Pos
 * @return true  Query success
 * @return false Query fail
 */
bool SqList::QueryValue(elem data, int *pos)
{
    SqListElem *temp_node = this->sq_list_header->sq_list_next;
    int count = 1;

    while(temp_node)
    {
        if(temp_node->data == data)
        {
            *pos = count;
            return true;
        }
        temp_node = temp_node->sq_list_next;
        count++;
    }
    return false;  
}

/**
 * @brief get value by specified pos 
 * 
 * @param pos     specified pos 
 * @param value   the value by specified pos 
 * @return true    get value success
 * @return false   get value fail
 */
bool SqList::GetPosValue(int pos, int *value)
{
    SqListElem *temp_node = this->sq_list_header;
    if(pos < 1 || pos > this->sq_list_length)
    {
        return false;
    }
    while(pos)
    {
        temp_node = temp_node->sq_list_next;
        pos--;
    }
    *value = temp_node->data;

    return true;
}

/**
 * @brief get sqList length
 * 
 * @return int sqList length
 */
int SqList::ListLength()
{
    return this->sq_list_length;
}

/**
 * @brief Delete the sqListNode by specified pos
 * 
 * @param pos specified pos
 * @return true    Delete the sqListNode Success
 * @return false   Delete the sqListNode Fail
 */
bool SqList::DeletePos(int pos)
{
    int temp = 0;
    SqListElem *temp_list_pri, *temp_list; // temp_list[0] 用于保存要删除节点的前一个节点，temp_list[1] 用于保存要删除的节点

    if(pos <=0 || pos > this->sq_list_length)
    {
        return false;
    }

    // 寻找要删除节点的头一个节点
    temp = pos-1;
    temp_list_pri = this->sq_list_header;
    while(temp)
    {
        temp_list_pri = temp_list_pri->sq_list_next;
        temp--;
    }

    // 保存要删除的节点，要与稍后删除此节点
    temp_list = temp_list_pri->sq_list_next;

    // 将要删除节点的后一个节点 作为 要删除节点的前一个节点 的 next 节点
    temp_list_pri->sq_list_next = temp_list->sq_list_next;

    delete temp_list;

    this->sq_list_length--;

    return true;
}

/**
 * @brief Insert node
 * 
 * @param pos    Insert node pos
 * @param value  Insert node pos value
 * @return true  Insert node success
 * @return false Insert node fail
 */
bool SqList::InsertNode(int pos, int value)
{
    int index = 0;

    SqListElem *temp = this->sq_list_header;

    if (pos < 1 || pos > this->sq_list_length + 1)
    {
        return false;
    }
    for(index = 1; index < pos; index++)
    {
        temp = temp->sq_list_next;
    }

    SqListElem *s = new SqListElem;

    s->sq_list_next = temp->sq_list_next;
    temp->sq_list_next = s;
    s->data = value;
    this->sq_list_length++;

    return true;
}

/**
 * @brief print all value in sqList
 * 
 */
void SqList::PrintAllValue()
{
    SqListElem *temp_node = this->sq_list_header->sq_list_next;
    int cnt = 1;
    
    cout << "The sqList length " << this->sq_list_length << endl;
    
    while(temp_node)
    {
        cout << "pos: " << cnt << " val: " << temp_node->data << endl;
        temp_node = temp_node->sq_list_next;
        cnt++;
    }
}


SqList *SqList::SortSqList(const SqList *oriSqlist)
{
    SqList *sq = new SqList;
    SqListElem *temp_node;
    int cnt = 0;

    sq->sq_list_header = new SqListElem;
    sq->sq_list_header->sq_list_next = NULL;
    sq->sq_list_length = 0;

    cnt = oriSqlist->sq_list_length;
    elem data[cnt] = {0};
    temp_node = oriSqlist->sq_list_header->sq_list_next;
    for(cnt; cnt>0; cnt--)
    {
        data[cnt-1] = temp_node->data;
        temp_node = temp_node->sq_list_next;
    }

    // 冒泡排序法
    elem temp_data = 0;
    cnt = oriSqlist->sq_list_length;
    for(int i=cnt; i>1; i--)
    {
        for(int j=1; j<i; j++)
        {
            if(data[j] < data[j-1])
            {
                temp_data =  data[j];
                data[j] = data[j-1];
                data[j-1] = temp_data;
            }
        }
    }

    cnt = oriSqlist->sq_list_length;
    temp_node = sq->sq_list_header;
    for(int k=0; k<cnt; k++)
    {
        SqListElem *s = new SqListElem;
        s->sq_list_next = temp_node->sq_list_next;
        temp_node->sq_list_next = s;
        s->data = data[k];
        sq->sq_list_length++;
        temp_node = s;
    }
    return sq;
}